1. Field of the Invention
The present invention is directed to a system and method for flood filling. Aspects of the present invention relate to anti-aliased flood filling without artifacts.
2. Description of the Related Art
FIG. 1 shows an original or initial image 50 with regions 52 defined by strokes or lines 54. FIG. 2 shows image 50 where a flood fill operation on the regions 52 in FIG. 1 has produced corresponding filled regions 72.
Flood filling is an important technique in two-dimensional computer graphics and has many uses such as coloring the cells of 2D cartoon characters, changing the color of a region in a photographic image, etc. A flood fill may also be applied to a three-dimensional surface, but the calculation is usually two-dimensional. Most imaging programs such as Adobe Photoshop, Painter, and GIMP, have a user tool for performing a flood fill operation. Typically, these tools allow a user to click a point on an image (a seed point) causing a surrounding patch or region of like-colored pixels to be filled with the user's choice of color. In image 50 in FIG. 1, the regions 52 were originally light colored patches bounded by dark colored pixels of the lines 54 (as discussed later, the dashed rectangular region 76 is shown blown-up in FIG. 3). After being flood filled, the same regions 52 (seen as regions 72 in FIGS. 2/3) exhibit the new fill color up to the pixels of the lines 54 that delimit the regions 52/72.
Flood filling a patch or region of an image with a fill color, fill image, fill function, fill pattern, etc., has usually entailed identifying contiguous pixels that have a same or similar color, and filling that region by setting its pixels to the fill color. Typically, the mutually contiguous pixels in the fill region have an initial color close to or the same as a given base color, usually referred to as a seed color. A color that is “close” may vary from the seed color by less than a specified tolerance. For identifying a fill region, there are many algorithms, most of which simply mark candidate pixels as being “in” or “out” of the region without performing any anti-aliasing.
A well-known flood filling technique is Alvy Ray Smith's tint fill algorithm (ACM Siggraph Proceedings, August 1979). Many flood-filling techniques are similar to Alvy Ray Smith's technique, which usually starts with an array of pixels (an image), a seed color (usually the color of the start pixel), and a destination fill color (the new color being filled in). Starting at the start pixel and working outward, neighboring pixels are recursively considered and added to the region if their color matches or approximates the seed color. The pixels added to the region are set to the fill color.
As seen above, a flood-filled region abuts differently colored pixels. Anti-aliasing has been used to smooth the meeting of these differing colors, for example by applying a blur to the fill region (or to a mask of the fill region). To understand anti-aliasing, it can help to think of an image as a discrete sampling, or “discretization”, of actual or hypothetical continuous colors. Generally, anti-aliasing smoothes the discretization of an image by padding pixels with intermediate colors. In the context of a flood fill operation, anti-aliasing has been computed by performing a flood fill type operation to create a “mask” image of the fill region, applying a slight blur to that mask, and then blending a color into the target image via the mask image. However, the anti-aliasing of this approach is at best a gross approximation of the theoretical correct solution, and as such several visual artifacts can be found in the results. Examples of such artifacts include haloing (see the light pixels between line 52 and region 72 in FIG. 3), failure to get into corners of the fill region, and others.
FIG. 3 shows problems that can occur with prior art anti-aliased flood filling. FIG. 3 is a blow-up of dashed rectangular region 76 in FIG. 2. As can be seen, pixels such as pixel 90 carry shades of the original background color 92 into the filled regions 72, creating a haloing effect. A flood fill is often blurred to emulate anti-aliasing, but insufficient blurring creates jagged edges, and too much blurring creates soft edges and haloes as in FIG. 3. There is no median approach that gives good anti-aliasing without a haloing. Previously, artifacts from anti-aliased flood filling have not been automatically correctable or avoidable.
There is a need to perform anti-aliased flood fill operations without producing visual artifacts.